解答1[Java]:
class Solution {
public String minWindow(String s, String t) {
int[] map = new int[128];
for (char c : t.toCharArray()) map[c]++;
int counter = t.length(), left = 0, right = 0, head = 0, d = Integer.MAX_VALUE;
while (right < s.length()) {
if (map[s.charAt(right++)]-- > 0) counter--;
while (counter == 0) {
if (right - left < d) d = right - (head = left);
if (map[s.charAt(left++)]++ == 0) counter++;
}
}
return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);
}
}
思路
注意 if (map[s.charAt(right++)]-- > 0)
这句,不论 right 指向位置的字符是哪个,在判断之后都会被减去 1。因为在前边的语句中,已经预先把 t 中的字符在 map 中加 1 了,所以只有不在 t 中的字符才会被减成负数。
同理,if (map[s.charAt(left++)]++ == 0) counter++;
如果判断为真,说明 left 指针指向的字符是 t 中的一个字符,且减去这个字符之后,这个字符的数量就不够了,因此需要把 counter 加1。如果 left 指向的不是 t 中的字符,那么这个字符在 map 中的值一定是负数,因为之前 right 遍历的时候被减过。
假设 t="ABC"
,当 counter 为零的时候,map['A']
、map['B']
和 map['C']
其中至少有两个的值是小于等于零的。可以小于零,但至少要等于零。不然 counter 是不会为零的。
当 map['A']
被减为零之后,如果再遇到字符 A
,就不会再减 counter 了。因为 map['A']
已经被减到零,说明前面已经匹配到的字符 A
的数量已经足够了。